#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

//class Solution {
//public:
//    bool search(std::vector<int>& nums, int target) {
//        int left = 0;
//        int right = nums.size() - 1;
//
//        while (left <= right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] == target)
//            {
//                return true;
//            }
//            if (nums[mid] < nums[right])
//            { // Right half is sorted
//                if (nums[mid] < target && target <= nums[right])
//                {
//                    left = mid + 1;
//                }
//                else
//                {
//                    right = mid - 1;
//                }
//            }
//            else if (nums[mid] > nums[right])
//            { // Left half is sorted
//                if (nums[left] <= target && target < nums[mid])
//                {
//                    right = mid - 1;
//                }
//                else
//                {
//                    left = mid + 1;
//                }
//            }
//            else
//            {
//                right--;
//            }
//        }
//
//        return false;
//    }
//};
//
//class Solution {
//public:
//    vector<vector<int>> ret;
//    void push(vector<int> v, int n, int k, int p, int l)
//    {
//        if (k == 0)
//        {
//            ret.push_back(v);
//            return;
//        }
//        if (p > n)
//        {
//            return;
//        }
//        for (int i = p; i <= n; i++)
//        {
//            vector<int> v1 = v;
//            if (!v1.empty())
//            {
//                if (i > v1[l - 1])
//                {
//                    v1.push_back(i);
//                    push(v1, n, k - 1, p + 1, l + 1);
//                }
//            }
//            else
//            {
//                v1.push_back(i);
//                push(v1, n, k - 1, p + 1, l + 1);
//            }
//        }
//    }
//    vector<vector<int>> combine(int n, int k) {
//        vector<int> v;
//        push(v, n, k, 1, 0);
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    void nextPermutation(vector<int>& nums) {
//        int n = nums.size();
//        if (n <= 1)
//        {
//            return;
//        }
//        int fast = n - 1;
//        int p = 0;
//        for (; fast > 0; fast--)
//        {
//            int slow = fast - 1;
//            for (; slow >= 0; slow--)
//            {
//                if (nums[fast] > nums[slow])
//                {
//                    swap(nums[slow], nums[fast]);
//                    p = 1;
//                    break;
//                }
//            }
//            if (p == 1)
//            {
//                break;
//            }
//        }
//        if (p == 0)
//        {
//            sort(nums.begin(), nums.end());
//        }
//    }
//};

struct ListNode {
 	int val;
 	struct ListNode *next;
 	ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode*& nodereverse(ListNode*& head, int n)
    {
        ListNode* node = head;
        while (n--)
        {
            node = node->next;
        }
        return node;
    }

    ListNode*& headreverse(ListNode*& head, int n)
    {
        ListNode* node1 = head;
        ListNode* node2 = nodereverse(head, n - 2);
        if (node1 == node2)
        {
            ListNode* node3 = node2->next->next;
            node2 = node2->next;
            node1->next = node3;
            node2->next = node1;
            return node2;
        }
        ListNode* x1 = node1->next;
        head = node2->next;
        node1->next = head->next;
        node2->next = node1;
        head->next = x1;
        return head;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        if (m == n)
        {
            return head;
        }
        if (1 == m)
        {
            return headreverse(head, n);
        }
        if (1 == n)
        {
            return headreverse(head, n);
        }
        ListNode* node1 = nodereverse(head, m - 2);
        ListNode* node2 = nodereverse(head, n - 2);
        if (node1->next == node2)
        {
            ListNode* node3 = node2->next;
            node1->next = node3;
            node2->next = node3->next;
            node3->next = node2;
            return head;
        }
        ListNode* x1 = node1->next->next;
        ListNode* x2 = node2->next;
        node1->next->next = x2->next;
        x2->next = x1;
        node2->next = node1->next;
        node1->next = x2;
        return head;
    }
};

void Print(ListNode* head)
{
    while (head)
    {
        cout << head->val << "->";
        head = head->next;
    }
    cout << endl;
}


int main()
{
    ListNode* node = new ListNode(1);
    ListNode* head = node;
    node->next = new ListNode(2);
    node = node->next;
    node->next = new ListNode(3);
    node = node->next;
    node->next = new ListNode(4);
    node = node->next;
    node->next = new ListNode(5);
    Solution s;
    Print(s.reverseBetween(head, 2, 4));
    return 0;
}